
The grammar defines the allowed structure of sentences. The grammar rules used in this project are standard BNF (Backus-Naur-Form) style rewrite rules, and loosely follows the rules in the course book \cite{russel_norvig}. For example the rule:
\begin{center}
 	\textbf{S $<$- NP VP}
\end{center}
states that the non-terminal symbol S can be rewritten by a NP (noun-phrase) followed by a VP (verb-phrase). The symbols on the right hand side can either be terminal or non-terminal symbols, where a terminal symbol simply is a wordcategory. For instance, REGN (which can represent a regular noun like \textit{banana}) is a wordcategory and a terminal symbol.

The parsing algorithm implemented in this project is a so called chart parser. This is a dynamic programming algorithm and uses a combination of top down and bottom up parsing in an efficient way. It doesn't have the weaknesses of neither top down nor bottom up parsing \cite{russel_norvig}.

The goal of parsing is to find a \textit{parse tree} representing a hierarchical structure of the sentence. The chart parser does not produce such a tree directly but outputs a datastructure called a \textit{chart}. This datastructure can be used to construct all possible parse trees (the grammar is often ambiguous and can produce several interpretations of a sentence) \cite{russel_norvig}. The implementation used considers only one parse tree (the first one found), and is therefore somewhat limited.
